public class Leetcode28 {

    public static void main(String[] args) {

    }

    private static final int MAX_RES = 1000000007;

    public int purchasePlans(int[] nums, int target) {
        if (nums == null || nums.length < 1) {
            return 0;
        }

        long res = 0;

        int[] hash = new int[target];

        for (int num : nums) {
            if (num >= target) {
                continue;
            }

            hash[num]++;
        }

        for (int i = 1; i < hash.length; i++) {
            hash[i] += hash[i - 1];
        }

        int sub;
        for (int num : nums) {
            if (num >= target) {
                continue;
            }

            sub = target - num;
            res += hash[sub];

            if (sub >= num) {
                res--;
            }
        }

        return (int) ((res >> 1) % MAX_RES);
    }

}
